Context Free Grammar

Definition

A context-free grammar $G = (V, Σ, S, R)$ ：
- $V$ : finite set of symbols
- $Σ \subseteq V$ : set of terminals
- $S \in V / Σ$ : start symbol
- $R \subseteq (V / Σ) \times V^{*}$ : finite set of rules
derive in one step: for any $x, y, u \in V^{*}$ , for any $A \in V / Σ$ , $x A y \Rightarrow_{G} x u y$ if $(A, u) \in R$ .
derives: for any $w, u \in v^{*}$ , $w \Rightarrow_{G}^{*} u$ if $w = u$ or $w \Rightarrow_{G} \dots \Rightarrow_{G} u$
A language is context-free is some CFG generates it.

Represent iambic String

$S \to e$
$S \to a$
$S \to b$
$S \to a S a$
$S \to b S b$

Give a context grammar that generates the

{x # y, | x | \neq | y |}

$T \to 0 | 1$
$A \to T A T | #$ , $| x | = | y |$
$L \to T L | A$ , $| x | \geq | y |$
$R \to R T | A$ , $| x | \leq | y |$
$s \to T L | R T$ , $| x | > | y |$ or $| x | < | y |$

Parse tree

internal nodes: non-terminals
leaves: terminals or $e$

Chomsky Norm Form

A CFG is in Chomsky Norm Form (CNF) if every of its rules is of three forms

$S \to e$
$A \to B C$ , $B, C \in V / Σ / {S}$
$A \to a$ , $a \in Σ$

Theorem: Every CFG has a equivalent CFG in CNF

Conflict conditions:（all of the conflicts can be transformed）

S appears on RHS
$A \to e$ , $A \neq S$
$A \to B$ , $B \in V, Σ$
$A \to u_{1} u_{2} \dots u_{k}$ , $k \geq 3$ and $u_{i} \in V$
$A \to u_{1} u_{2}$ , $u_{1} \in Σ$ or $u_{2} \in Σ$

PDA

Push-down automata: A PDA is 6-tuple $P = (K, Σ, Γ, Δ, s, F)$

$Γ$ : stack alphabet
$Δ$ : transition relation
- a 'finite' subset of $(K \times (Σ \cup {e}) \times Γ^{*}) \times (K \times Γ^{*})$
- The first $K$ is the current state
- The $Σ \cup {e}$ is the symbol read
- The first $Γ^{*}$ means that pop a string from the top of stack
- The second $K$ is the next state
Configuration
- A configuration for P is a member of $K \times Σ^{*} \times Γ^{*}$
- $(p, x, α) ⊢_{P} (q, y, β)$ if $\exists ((p, a, r), (q, η)) \in Δ$ . s.t. $x = a y$ , $α = r τ$ and $β = η τ$ for some $τ \in Γ$
- $(p, x, α) ⊢_{P}^{*} (q, y, β)$
Language
- $L (P) = {w \in Σ^{*} : P a c c e p t s w}$
$P$ accepts $w \in Σ^{*}$ if $(s, w, e) ⊢_{P}^{*} (q, e, e)$ for some $q \in F$
- $q$ is final state
- the stack is empty
N-PDA > D-PDA，这里讨论的主要是 N-PDA

Construct PDA accepts

L = {w \in {0, 1}^{*} : # 0^{'} s = # 1^{'} s i n w}

PDA 不好表示空栈，故可以使用字符 $ 进行标记

$K = {s, q, f}$
$S = s$
$F = {f}$
$Σ = {0, 1}$
$T = {0, 1, $}$
$δ =$
- ${((s, e, e), (q, $))$
- $((q, 1, $), (q, 1))$
- $((q, 0, $), (q, 0))$
- $((q, 1, 1), (q, 11))$
- $((q, 0, 1), (q, e))$
- $((q, 1, 0), (q, e))$
- $((q, 0, 0), (q, 00))$
- $((q, e, $), (f, e))}$

Prove

S u f (A) = {v \in Σ^{*} : \exists u \in Σ^{*}, u v \in A}

A

is context-free, so is

S u f (A)

for $P = (K, Σ, T, Δ, s, F)$ , construct $P^{'} = (K^{'}, Σ, T, Δ^{'}, s, F)$
$Δ^{'} = {((p^{'}, e, α), (q^{'}, β)) | ((p, a, α), (q, β)) \in Δ} \cup {(p^{'}, e, e), (p, e) | p \in K}$

A language is context-free if and only if it is accpeted by some PDA.

C F G \leftrightarrow P D A

Given $G = (V, Σ, S, R)$ , Construct $P = (K, Σ, T, Δ, s, F)$

$K = {s, f}$
$F = f$
$T = V$
$Δ =$
- $((s, e, e), (f, S))$
- $((f, e, A), (f, u))$ , for each $(A, u) \in R$
- $((f, a, a), (f, e))$ , for each $a \in Σ$

Closure property

Union: $\cup$
Concatenation: $\circ$
Star: $*$
not close for intersection: $\cap$
- $C F L \cap R L = C F L$
not close for difference set: $\bar{A}$

Provement of Closure property

$L_{1} \cup L_{2}$ : $S \to S_{1} | S_{2}$
$L_{1} \circ L_{2}$ : $S \to S_{1} S_{2}$
$L^{*}$ : $S \to S S | e$
$L^{R}$
- transform to CFG
- $A \to B C$ : $A \to C B$

Pumping Theorem for CFL

Let $L$ be a context-free language. There exists an integer $p > 0$ such that any $w \in L$ with $| w | \geq p$ can divided into five pieces $w = u v x y z$ satisfying:

$u v^{i} x y^{i} z \in L$ for $i \geq 0$
$| v | + | y | > 0$
$| v x y | \leq p$

Prove

{a^{n} b^{n} c^{n} : n \geq 0}

is not context-free

Assume if is CFL
Let $p$ be the pumping length, pick $w = a^{p} b^{p} c^{p} \in L$
By pumping theorem, $w = u v x y z$ s.t.

$u v^{i} x y^{i} z \in L$ for $i \geq 0$
$| v | + | y | > 0$
$| v x y | \leq p$

(3) -> at most one of a or c do apprear in v and y
(2) -> $u v^{0} x y^{0} z \notin L$
Contradicts with (1)

Pumping Theorem for CFL 的技巧

使用类似 滑动窗口 的方法，设置窗口大小为 p，在枚举的字符串中滑动，并穷举所有的情况。